package com.wyx.suanfa;

import java.util.Scanner;

/**
 * @author 王艺锡
 * @version 1.0
 */
public class largestRectangleArea {
    //给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
    //
    //求在该柱状图中，能够勾勒出来的矩形的最大面积。
    public static void main(String[] args) {

    }
}
/*
* class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int[] minLeftIndex = new int[len];
        int[] minRightIndex = new int[len];
        // 记录每个柱子 左边第一个小于该柱子的下标
        minLeftIndex[0] = -1;
        for(int i = 1;i<len;i++){
            //从当前柱子的前一个柱子开始找
            int temp = i - 1;
            //如果此柱子大于等于当前柱子的高度，就找此柱子 左边第一个小于此柱子的下标
            while(temp >=0 && heights[temp] >= heights[i]){
                temp = minLeftIndex[temp];
            }
            minLeftIndex[i] = temp;
        }
        // 记录每个柱子 右边第一个小于该柱子的下标
        minRightIndex[len - 1] = len;
        for(int i = len - 2;i>=0;i--){
            //从当前柱子的后一个柱子开始找
            int temp = i + 1;
            //如果此柱子大于等于当前柱子的高度，就找此柱子 右边第一个小于此柱子的下标
            while(temp < len && heights[temp] > heights[i]){
                temp = minRightIndex[temp];
            }
            minRightIndex[i] = temp;
        }
        //记录最大面积
        int sum = 0;

        for(int i = 0;i<len;i++){
            //当前柱子的高度
            int h = heights[i];
            //宽度
            int w = (minRightIndex[i] - minLeftIndex[i]) - 1;
            //当前柱子与相邻柱子所围成的最大面积
            int result = h * w;
            //如果比当前遍历到的最大面积大,就替换
            sum = Math.max(sum,result);
        }
        return sum;
    }
}*/
